Search for: All records

We motivate and visualize problems and methods for packing a set of objects into a given container, in particular a set of different-size circles or squares into a square or circular container. Questions of this type have attracted a considerable amount of attention and are known to be notoriously hard. We focus on a particularly simple criterion for deciding whether a set can be packed: comparing the total area A of all objects to the area C of the container. The critical packing density δ∗ is the largest value A/C for which any set of area A can be packed into a container of area C. We describe algorithms that establish the critical density of squares in a square (δ∗ = 0.5), of circles in a square (δ∗ = 0.5390 . . .), regular octagons in a square (δ∗ = 0.5685 . . .), and circles in a circle (δ∗ = 0.5). 2012 ACM Subject Classification Theory of computation → Packing and covering problems; Theory of computation → Computational geometry